#ifndef SOLUTION_H_
#define SOLUTION_H_
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;

class Solution {
public:
	int largestRectangleArea(vector<int> &height) {
		// Start typing your C/C++ solution below
		// DO NOT write int main() function

		if(height.size() <= 0)
			return 0;

		if(1 == height.size())
			return 1*height[0];


		vector<int> lis(height.size(),0), ris(height.size(),0);
		stack<size_t> pres;
		for(size_t i=0;i<height.size();i++)
		{
			while(!pres.empty())
			{
				if(height[pres.top()] >= height[i])
					pres.pop();
				else
					break;
			}
			if(pres.empty())
				lis[i] = i;
			else
				lis[i] = i - pres.top() - 1;
			pres.push(i);
		}

		while(!pres.empty()) pres.pop();


		for(size_t idx=height.size();idx>0;idx--)
		{
			size_t i = idx-1;
			while(!pres.empty())
			{
				if(height[i] <= height[pres.top()])
					pres.pop();
				else
					break;
			}
			if(pres.empty())
				ris[i] = height.size() - i - 1;
			else
				ris[i] = pres.top() - i - 1;

			pres.push(i);
		}

		int maxArea = 0;
		
		for(size_t i=0;i<height.size();i++)
		{
			int curMax = (lis[i]+ris[i]+1)*height[i];
			maxArea = max(curMax,maxArea);
		}

		return maxArea;

	}
};
#endif